#
# 6.863 -- Final Project
#
# Author: Andreea Bodnari
# Contact: andreeab@mit.edu
# 5/14/11
#

from populate.Populate import *
import math
import operator

class Evaluate():
    
    INFINITY = "infinity"
    
    def __init__(self, rows, cols):
        self.rows  = rows
        self.cols = cols
        
        # output files
        self.sentences = "../experiments/Sentences.txt"
        fileOutput = open(self.sentences, "w")
        fileOutput.close()
        
        self.probabilities = "../experiments/Probabilities.txt"
        fileOutput = open(self.probabilities, "w")
        fileOutput.close()
        
    def getProbabilityMatrix(self, aGrid):
        '''
        Returns a probability matrix from an input grid
        
        @param aGrid: the input grid 
        @return: the probability matrix associated with the grid
        '''
        matrix = []
        
        grid = aGrid.grid

        for len in range(self.rows):
            matrix.append([])
        
        for row in range(self.rows):
            for col in range(self.cols):
                prob = float(grid[row][col][1] )
                if prob  == 0.:
                    prob = self.INFINITY
                else:
                    prob = -1 *  math.log(prob)
                    
                matrix[row].append(prob)
                
        return matrix
    
    def pathFinder(self, grid, start):
        '''
        Find the most likely path in a constructed grid
        using the Dijkstra algorithm
        
        @param grid: the grid under analysis
        @param start: the start position for finding the most optimal path  
        '''
        matrix = self.getProbabilityMatrix(grid)
        distanceMatrix = []
        previous = []
        
        for len in range(self.rows):
            distanceMatrix.append([]) 
            previous.append([])
            
        for row in range(self.rows):
            for col in range(self.cols):
                distanceMatrix[row].append(self.INFINITY) 
                previous[row].append(0)
                
        # init step
        distanceMatrix[start[0]][start[1]] = 0
        setOfNodes = {start:0}
#
#        d_i = [1,1,1,0,0,-1,-1,-1]
#        d_j = [-1, 0,1,-1,1,-1,0,1]
        
        d_i = [1,0]
        d_j = [0,1]
#        
        minNode = (0,0)
        minVal = 10000000000.0
        
        while setOfNodes :
            sortedNodes = sorted(setOfNodes.iteritems(), key=operator.itemgetter(1))

            bestNode = sortedNodes[0][0]
                            
            if grid.grid[bestNode[0]][bestNode[1]][0] == '.':
                if minVal > setOfNodes.get(bestNode):
                    minVal = setOfNodes.get(bestNode)
                    minNode = bestNode
                
            del setOfNodes[bestNode]
            
            for val in range(0, 2):
                newIndex_i = bestNode[0] + d_i[val] 
                newIndex_j = bestNode[1] + d_j[val]
                
                if (0 <= newIndex_i < self.rows and 0 <= newIndex_j < self.cols ):
                    if matrix[newIndex_i][newIndex_j] == self.INFINITY :
                        pass
                    
                    elif distanceMatrix[newIndex_i][newIndex_j] == self.INFINITY or distanceMatrix[bestNode[0]][bestNode[1]] + matrix[newIndex_i][newIndex_j] < distanceMatrix[newIndex_i][newIndex_j]:
                        distanceMatrix[newIndex_i][newIndex_j] = distanceMatrix[bestNode[0]][bestNode[1]] + matrix[newIndex_i][newIndex_j]
                        setOfNodes[(newIndex_i,newIndex_j)] = distanceMatrix[newIndex_i][newIndex_j]
                        previous[newIndex_i][newIndex_j] = bestNode
        
        return self.tracePath(previous, minNode, start, grid.grid)
    
    def tracePath(self, previous, minNode, start, grid):
        '''
        Trace the smallest path using the trace matrix
        @param previous: the trace matrix
        @param minNode: the  minimum node from where we start the back trace
        @param start: the last element in the trace
        @param grid: the grid from which the trace originated
        
        @return: the traced path and the words and probabilities associated with it  
        '''
        path = []
        words = []
        probs = []
        
        currentNode = minNode
        
        while currentNode <> start:
            path.append(currentNode)
            words.append(grid[currentNode[0]][currentNode[1]][0])
            probs.append(grid[currentNode[0]][currentNode[1]][1])
            currentNode = previous[currentNode[0]][currentNode[1]]

        path.append(start)
        words.append(grid[start[0]][start[1]][0])
        probs.append(grid[start[0]][start[1]][1])
        
        path.reverse()
        words.reverse()
        probs.reverse()
        
        # print the words to the output file 
        fileOutput = open(self.sentences, "a")
        strOut = ""
        
        for el in words:
            strOut += el + " "
        fileOutput.write(strOut.strip(" ") + "\n")
        fileOutput.close()
        
        totalProb = 1.
        for val in probs:
            if val <> 0.:
                totalProb = totalProb * float(val)
        
        fileOutput = open(self.probabilities, "a")
        fileOutput.write(str(totalProb))
        fileOutput.write("\n")
        fileOutput.close()
        
        return (words, probs, path)

        
        
        
        
        
        